package com.song.tree;

/**
 *  二叉树排序
 *  构建一个排好序的二叉树
 *  按中序输出 就是排序结果
 */
public class BinSortTest {

    public BinSortTest(){
        System.out.println("BinSortTest 初始化");
    }
    class Node {
        Node leftChild = null;
        Node rightChild = null ;
        int data;
        public Node(){
            System.out.println("Node 内部类加载");
        }
        public Node(int a){
            this.data = a ;
        }
    }
    static Node root = null;
    Node node1 = null ;
    public void createTree(int[] a ){
        for (int i = 0 ; i < a.length ; i++){
            node1 = new Node(a[i]);
            root =  insertNode(root,node1);
        }

    }

    public Node insertNode(Node root, Node node) {
        if (root == null) {
            root = node;
            return root;
        }

        if (node.data < root.data) {
            if (root.leftChild == null) {
                root.leftChild = node ;
            }else{
                insertNode(root.leftChild, node);
            }

        } else {
            if (root.rightChild == null ){
                root.rightChild = node ;
            }else{
                insertNode(root.rightChild, node);
            }
        }
        return root;
    }


    public Node deleteNode(Node node , int key ){
        Node root = node ;
        if(node == null){
            System.out.println("删除的节点不存在！");
            return root ;
        }
        if (node.data > key ){
            deleteNode(node.leftChild , key);
        }else if (node.data < key ){
            deleteNode(node.rightChild , key);
        }else if(node.data == key){   // node = key
            if (node.leftChild == null ){
                node = node.rightChild ;
            }else if (node.rightChild == null){
                node = node.leftChild ;
            }else{
                Node node2 = node.rightChild;
                Node node3 = new Node();  //保存node2的父级
                while(node2.leftChild != null){
                    node3 = node2 ;
                    node2 = node2.leftChild ;  //找到要替换的节点
                }
                node.data = node2.data ;
                node3.leftChild = null ; //这个地方不能node2 = null ; （可能是因为java引用问题，相当于复制，而不是修改本身 所以引入一个父级 ）
            }
        }else{
            System.out.println("删除的节点不存在！");
        }
        return root ;
    }

    public void printRoot(int a){
        System.out.println(a+" ");
    }
    //中序遍历
    public void pre(Node root) {
        if (root != null ) {
            pre(root.leftChild);
            printRoot(root.data);
            pre(root.rightChild);
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{20,100,52,8,6,9,4,1,3,8,7,898,451,56,68,200,215,345,198};
        BinSortTest binSort = new BinSortTest();
        binSort.createTree(a);
        binSort.pre(root);  //root为静态时，可用
        System.out.println("========");
        Node node = binSort.deleteNode(root, 101);
        binSort.pre(node);
        // binSort.pri();
    }
}
